package tree.heap.myDefinedGraphHeap;

import figureAndGraph.Node;
import lombok.Data;

import java.util.HashMap;
import java.util.Map;

/**
 * 功能描述:定义图堆 : dijkstra 使用: 小顶推的实现
 * 2024/07/10
 *
 * @author ZhangYi
 */
public class DefinedGraphHeap {
	@Data
	public static class NodeRecod{
		private int distince; // 到该节点的距离
		private Node node; // 节点

		public NodeRecod(int distince, Node node) {
			this.distince = distince;
			this.node = node;
		}
	}

	public static class MyGraphHeap {

		private NodeRecod[] heap; // 堆上的元素
		private Map<NodeRecod, Integer> heapIndexMap; // 堆上的元素在数组中的索引, -1 表示不在堆上,但是在堆上存在过
		private Map<NodeRecod, Integer> nodeIndexMap; // 节点在堆上的索引
		private int size; // 堆上的元素个数

		public MyGraphHeap(int size) {
			this.heap = new NodeRecod[size];
			this.heapIndexMap = new HashMap<>(size);
			this.nodeIndexMap = new HashMap<>(size);
			this.size = 0;
		}

		private void heapInsert(NodeRecod node, int index) {
//			Integer index = nodeIndexMap.get(node);
			// 上浮的过程, 只需要看 当前节点的父节点
			while (heap[index].distince < heap[(index - 1) / 2].distince) {
				swapRecord(index, (index - 1) / 2);
				index = (index - 1) / 2;
			}

		}

		private void swapRecord(int index, int index2) {
			this.nodeIndexMap.put(heap[index],index2);
			this.nodeIndexMap.put(heap[index2],index);
			this.heapIndexMap.put(heap[index],index2);
			this.heapIndexMap.put(heap[index2],index);

			NodeRecod temp = heap[index];
			heap[index] = heap[index2];
			heap[index2] = temp;
		}


		private void heapfiy(int index,int heapSize){
//			int index = nodeIndexMap.get(node).intValue();
			int leftIndex = index * 2 + 1;
			while (leftIndex < heapSize){
				int smallestIndex = leftIndex + 1 < heapSize && heap[leftIndex + 1].distince < heap[leftIndex].distince   ? leftIndex + 1 : leftIndex;

				smallestIndex = heap[smallestIndex].distince < heap[index].distince ? smallestIndex : index;
				if (smallestIndex == index){
					break;
				}
				swapRecord(smallestIndex,index);
				index = smallestIndex;
				leftIndex = index * 2 + 1;
			}

		}
		public NodeRecod pop() {
			NodeRecod nodeRecod = this.heap[0];
			swapRecord(0,--size);
			heapfiy(0,size);
			this.heapIndexMap.put(nodeRecod,-1);
			return nodeRecod;
		}


		public void push(NodeRecod nodeRecod){
			this.heap[size] = nodeRecod;
			this.heapfiy(0,size);
			this.heapInsert(nodeRecod,size++);
		}


		public void addOrUpdateOrIgnore(NodeRecod nodeRecod){
			if (inHeap(nodeRecod)) {
				int nodeIndex = heapIndexMap.get(nodeRecod).intValue();
				nodeRecod.distince = Math.min(this.heap[nodeIndex].distince,nodeRecod.distince);
				heapfiy(nodeIndexMap.get(nodeRecod),size);
			}
			if (!isEntered(nodeRecod)){
				this.heap[size] = nodeRecod;
				this.heapIndexMap.put(nodeRecod,size);
				this.nodeIndexMap.put(nodeRecod,size);
				heapInsert(nodeRecod,size++);
			}
		}

		/**
		 * 为空
		 *
		 * @return boolean
		 * @author ZhangYi
		 */
		public boolean isEmpty() {
			return size == 0;
		}

		/**
		 * 是否进入过堆
		 *
		 * @param node 节点
		 * @return boolean
		 * @author ZhangYi
		 */
		public boolean isEntered(NodeRecod node) {
			return heapIndexMap.containsKey(node);
		}

		/**
		 * 在堆中
		 *
		 * @param node 节点
		 * @return boolean
		 * @author ZhangYi
		 */
		public boolean inHeap(NodeRecod node) {
			return isEntered(node) && heapIndexMap.get(node) != -1;
		}
	}
}
